package main.java.exercise;

import main.java.framework.StudentInformation;
import main.java.framework.StudentSolution;

import java.util.Arrays;

public class StudentSolutionImplementation implements StudentSolution {
    @Override
    public StudentInformation provideStudentInformation() {
        return new StudentInformation(
                "", // Vorname
                "", // Nachname
                "" // Matrikelnummer
        );
    }

    private int calculateRopeFragmentationNaive(int length, int[] pricePerLength, int[] numberOfPiecesPerLength, int currentLength, int currentSum) {
        if (currentLength > length || length < 0)
            return currentSum;

        int[] witharray = numberOfPiecesPerLength.clone();
        // pack element and consider next
        int with = calculateRopeFragmentationNaive(
                length - currentLength,
                pricePerLength,
                witharray,
                1,
                currentSum + pricePerLength[currentLength]
        );
        int[] withoutarray = numberOfPiecesPerLength.clone();
        // don't pack element and consider next
        int without = calculateRopeFragmentationNaive(
                length,
                pricePerLength,
                withoutarray,
                currentLength + 1,
                currentSum
        );

        if (with > without) {
            witharray[currentLength] += 1;
            System.arraycopy(witharray, 0, numberOfPiecesPerLength, 0, witharray.length);
            return with;
        } else {
            System.arraycopy(withoutarray, 0, numberOfPiecesPerLength, 0, withoutarray.length);
            return without;
        }
    }

    public void calculateRopeFragmentationNaive(int length, int[] pricePerLength, int[] numberOfPiecesPerLength) {
        calculateRopeFragmentationNaive(length, pricePerLength, numberOfPiecesPerLength, 1, 0);
    }

    private void findSolution(int[][] solution, int[] pricePerLength, int length) {
        for (int i = 1; i < pricePerLength.length; i++) {
            for (int j = 0; j <= length; j++) {
                // if length of currently considered element exceeds maxLength,
                // copy solution where element wasn't considered
                if (i > j)
                    solution[i][j] = solution[i - 1][j];
                // else, try to find a solution where element is incorporated
                else {
                    // consider repetitions of previous elements, where i
                    // represents a bound for elements to consider repetitions
                    // for
                    for (int k = 1; k <= i; k++) {
                        // update if taking k again yields a better solution
                        solution[i][j] = Math.max(
                                pricePerLength[k] + solution[i][j - k],
                                solution[i][j]
                        );
                    }
                    // update if solution where element wasn't considered
                    // yields better results
                    solution[i][j] = Math.max(
                            solution[i - 1][j],
                            solution[i][j]
                    );
                }
            }
        }
    }

    private void backtrackSolution(int[][] solution, int[] pricePerLength, int length, int[] numberOfPiecesPerLength) {
        int i = pricePerLength.length - 1;
        int j = length;

        // either no elements or no more rope to cut is left
        while (i > 0 && j > 0) {
            // if current solution is a copy of the solution without the
            // current element, skip this element
            if (solution[i][j] == solution[i - 1][j]) {
                --i;
                continue;
            }

            // consider repeatedly taken elements
            boolean is_repeat = false;
            for (int k = 1; k <= i; k++) {
                if (solution[i][j - k] == solution[i][j] - pricePerLength[k]) {
                    numberOfPiecesPerLength[k] += 1;
                    j -= k;
                    is_repeat = true;
                    break;
                }
            }

            // for repeatedly taken elements, continue, in case other elements
            // were also taken repeatedly
            if (is_repeat)
                continue;

            // in all other cases, element i is part of the optimal solution,
            // which is why element is unconditionally taken
            numberOfPiecesPerLength[i] += 1;
            j -= i;
            --i;
        }
    }

    public void calculateRopeFragmentationDynProg(int length, int[] pricePerLength, int[] numberOfPiecesPerLength) {
        int[][] solution = new int[pricePerLength.length][length + 1];
        // find solution dynamically
        findSolution(solution, pricePerLength, length);
        // backtrack dynamically found solution
        backtrackSolution(solution, pricePerLength, length, numberOfPiecesPerLength);
        /*
        System.out.println(length);
        System.out.println(Arrays.toString(pricePerLength));
        System.out.println(Arrays.toString(numberOfPiecesPerLength));
        for (int[] a : solution)
            System.out.println(Arrays.toString(a));
         */
    }

}
